package com.lyt.springboot.util.algorithm;

import java.util.ArrayList;

public class S28 {
    ArrayList<String> res = new ArrayList<>();
    StringBuilder s = new StringBuilder();
    public ArrayList<String> Permutation(String str) {
        char[] chars = str.toCharArray();
        dfs2(chars,0,new boolean[chars.length]);
        ArrayList<String> res0 = new ArrayList<>();
//        for(String a:res) {
//            if(!res0.contains(a)) {
//                res0.add(a);
//            }
//        }
        return res;
    }
    public void dfs2(char[] chars,int depth,boolean[]used) {
        if(chars.length == depth) {
            res.add(new String(s));
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if(i>=1 && chars[i] == chars[i-1] && used[i-1]) {
                continue;
            }
            if(!used[i]) {
                used[i] = true;
                s.append(chars[i]);
                dfs2(chars,depth+1,used);
                //回退
                used[i] = false;
                 s.deleteCharAt(s.length()-1);

            }
        }
    }
    public static void main(String[] args) {
        S28 s28 = new S28();
        String a = "aab";
        ArrayList<String> permutation = s28.Permutation(a);
        System.out.println(permutation);
    }

}
